【LeetCode 15】3sum 三数之和

发表于 | 分类于

【LeetCode 15】3sum 三数之和

问题描述:

给定一个包含 n 个整数的数组 nums，判断 nums 中是否存在三个元素 a，b，c ，使得 a + b + c = 0 ？找出所有满足条件且不重复的三元组。

说明：答案中不可以包含重复的三元组。

示例:

1
2
3
4
5
6
7
例如, 给定数组 nums = [-1, 0, 1, 2, -1, -4]，

满足要求的三元组集合为：
[
  [-1, 0, 1],
  [-1, -1, 2]
]

Solution:

Solution 1: 首先想到的是以2sum为基础的利用集合解决的方法，用一个map存储所有元素，但是不能判断map重元素是否出现多次，两层循环，外层循环即为待处理的num，如果当前num在之前被处理过则跳过（用set除重复），与当前元素匹配的剩余两个元素组成的不重复三元组只可能出现在当前num之后，还要判断第三个元素与第二个元素并不为同一个元素，map中若有重复元素，其下标值为后放入者，这样便可判断不能判断map重元素是否出现多次问题，但是这种解决方法最耗时的地方在于结果集合去重，即每个结果先排序在放入set去重。

Code:

beat 14%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
      Map<Integer, Integer> twosum = new HashMap<>();
        List<List<Integer>> res = new ArrayList<>();
        if (nums.length < 3)
            return res;
        for (int i = 0; i < nums.length; i++)
            twosum.put(nums[i], i);
        Set<Integer> set = new HashSet<>();
        Set<List<Integer>> s = new HashSet<>();
        for (int i = 0; i < nums.length; i++) {
            int target = 0 - nums[i];
            if (set.contains(target))
                continue;
            set.add(target);
            for (int j = i + 1; j < nums.length; j++) {
                if (twosum.containsKey(target - nums[j])) {
                    if (twosum.get(target - nums[j]) > i + 1 && twosum.get(target - nums[j]) != j) {
                        List<Integer> list = new ArrayList<>();
                        list.add(nums[i]);
                        list.add(nums[j]);
                        list.add(target - nums[j]);
                        Collections.sort(list);
                        s.add(list);
                    }
                }
            }
        }
        for (List<Integer> l : s)
            res.add(l);
        return res;
    }
}

Solution 2：
先将数组排序，这样跳过已经处理过的元素与与上一个元素比较即可，外层循环记录待处理的num，内层循环用两个指针跳过重复元素，这样避免了结果解得去重；

Code:

beat 89%
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
 List<List<Integer>> lists = new ArrayList<List<Integer>>();
	        int length = nums.length;
	        Arrays.sort(nums);
	        for (int k = 0; k < length; k++) {
	            if ( nums[k] > 0 ){
	                break;
	            }
	            if ( k > 0 && nums[k] == nums[k-1] ){
	                continue;
	            }
	            int i = k + 1;
	            int j = length-1;
	            while( i < j )
	            {
	                int sum = nums[i] + nums[j] + nums[k];
	                if ( sum < 0 )++i;
	                else if ( sum > 0 )--j;
	                else
	                {
	                    lists.add(Arrays.asList(nums[i], nums[j], nums[k]));
	                    do{ ++i; } while( i < j && nums[i-1] == nums[i] );
	                    do{ --j; } while( i < j  && nums[j] == nums[j+1] );
	                }
	            }
	        }
	        return lists;
    }
}
Thanks!